'''
把数组写成一个方阵，并把对角线元素赋值为1，然后每一行的乘积对于B中的各个元素值。
比如{3，4，5}：
1 4 5
3 1 5
3 4 1
B = [1x4x5,3x1x5,3x4x1]
不知道有没有说清楚。无奈评论不能带图，可以参考那个上三角、下三角的思路和图。加油！
'''

'''
左数组是数字左边数的乘积
右数组是数组右边数的乘积
返回一个数的时候直接左边*右边
'''

'''
空间优化
'''
class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        l, r = [1] * n, [1] * n
        for i in range(1, n):
            l[i] = l[i - 1] * nums[i - 1]
        for i in range(n - 2, -1, -1):
            r[i] = r[i + 1] * nums[i + 1]
        res = []
        for i in range(n):
            res.append(l[i] * r[i])
        return res
'''
细节在于边界条件
1. 左数组需要从1到n(实际只到了n-1) 没有从0开始 因为i-1需要+1位
2. 于是右数组需要从n-2到-1(实际只到了0) 没有从n-1开始是因为 i+1也需要+1位
'''
class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        L,R = [1]*n,[1]*n
        for i in range(1,n):
            L[i] = L[i-1]*nums[i-1]
        for j in range(n-2,-1,-1):
            R[j] = R[j+1]*nums[j+1]
        res = []
        for i in range(n):
            res.append(L[i]*R[i])
        return res

